#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

// 只有输入输出时的下标是从1开始的，其余都为从0开始
struct Event {
    int time;        // 事件发生的时间
    int car_id;      // 车辆的ID
    int current_node; // 车辆当前所在的节点
    Event(int t, int c, int n) : time(t), car_id(c), current_node(n) {}

    // 重载对于Event的比较操作，使其原本是<的逻辑改为大于
    // 剩余等待时间越短越先出队
    bool operator<(const Event& next) const {
        return this->time > next.time;
    }
};

// Dijkstra算法，用于计算最短路径
vector<int> dijkstra(int N, int start, int end, int** roadlength, int** flow, int** restrictions) {
    int* dist = new int[N];      // 存储从起点到各节点的最短距离
    int* prev = new int[N];      // 存储路径中每个节点的前驱节点
    bool* visited = new bool[N]; // 记录节点是否已被访问

    // 初始化距离和访问状态
    for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[start] = 0;             // 起点到自身的距离为0
    prev[start] = -1;            // 起点没有前驱节点

    // 使用优先队列来实现Dijkstra算法
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int u = pq.top().second; // 当前节点
        pq.pop();
        if (visited[u]) continue; // 如果节点已被访问，跳过
        visited[u] = true;

        // 遍历所有相邻节点
        for (int v = 0; v < N; v++) {
            if (roadlength[u][v]<INT_MAX && flow[u][v]< restrictions[u][v]) {
                // 如果找到更短的路径，更新距离和前驱节点
                if (dist[v] > dist[u] + roadlength[u][v]) {
                    dist[v] = dist[u] + roadlength[u][v];
                    prev[v] = u;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
    }

    // 构建最短路径
    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = prev[node];
    }
    reverse(path.begin(), path.end()); // 反转路径，使其从起点到终点

    delete[] dist;
    delete[] prev;
    delete[] visited;
    return path;
}

int main() {
    int N, M;
    cin>>N>>M;

    // 动态分配二维数组
    int** roadlength=new int*[N];    // 存储道路长度
    int** restrictions=new int*[N];  // 存储道路的流量限制
    int** cars=new int*[M];          // 存储每辆车的起点和终点

    for (int i=0;i<N;i++) {
        roadlength[i]=new int[N];
        restrictions[i]=new int[N];
    }
    for (int i=0;i<M;i++) {
        cars[i]=new int[2];
    }

    //读取道路长度
    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            cin>>roadlength[i][j];
            if (roadlength[i][j]==0&&i!=j)roadlength[i][j]=INT_MAX; 
            //如果道路长度为0，则距离为无穷大
        }
    }

    //读取道路的流量限制
    for (int i=0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    //读取每辆车的起点和终点
    for (int i=0;i<M;i++) {
        cin>>cars[i][0]>>cars[i][1];
        cars[i][0]--; //将输入的起点和终点转换为从0开始的索引
        cars[i][1]--;
    }

    // 初始化流量矩阵
    int** flow=new int*[N];
    for (int i=0;i<N;i++) {
        flow[i]=new int[N];
        for (int j=0;j<N;j++) {
            flow[i][j]=0; // 初始化流量为0
        }
    }

    // 为每辆车找到初始路径，并设置事件
    priority_queue<Event> event_queue;
    vector<vector<int>> paths(M);      // 存储每辆车的路径
    vector<vector<int>> history(M);    // 存储每辆车的历史路径
    vector<int> car_arrival_time(M,-1); // 存储每辆车的到达时间，初始为-1

    for (int i = 0; i < M; i++) {
        paths[i] = dijkstra(N, cars[i][0], cars[i][1], roadlength, flow, restrictions);
        if (paths[i].size()==0){
            //如果无法到达，处理错误
            continue;
        }

        // 确保起点在路径中
        if (paths[i][0]!=cars[i][0]) {
            paths[i].insert(paths[i].begin(),cars[i][0]);
        }

        // 记录历史路径
        history[i]=paths[i];

        if (paths[i].size()>1) {
            int u = paths[i][0];
            int v = paths[i][1];
            int time = roadlength[u][v];
            event_queue.push(Event(time, i, v)); // 将车辆移动事件加入队列
            flow[u][v]++; // 更新流量
            flow[v][u]++;

            // 从路径中移除起点，因为车辆已经从起点出发
            paths[i].erase(paths[i].begin());
        } else {
            // 如果已经在目的地
            car_arrival_time[i] = 0;
            // history[i] 已经包含了起点
        }
    }

    // 模拟过程
    vector<int> to_plan;
    while (!event_queue.empty()) {
        int current_time = event_queue.top().time; // 当前时间

        // 处理所有时间相同的事件
        vector<Event> current_events;
        while (!event_queue.empty() && event_queue.top().time == current_time) {
            current_events.push_back(event_queue.top());
            event_queue.pop();
        }

        // 首先，处理所有到达事件：更新流量
        for (Event e : current_events) {
            int car_id = e.car_id;
            int current_node = e.current_node;

            // 如果车辆还没有到达目的地
            if (car_arrival_time[car_id] == -1) {
                // 从当前道路上移除车辆
                if (!paths[car_id].empty()) {
                    int u = paths[car_id].front();
                    int v = current_node;
                    flow[u][v]--; // 更新流量
                    flow[v][u]--;
                    paths[car_id].erase(paths[car_id].begin());
                }

                // 检查车辆是否到达目的地
                if (current_node == cars[car_id][1]) {
                    car_arrival_time[car_id] = current_time;

                    // 如果历史路径中还没有目的地，将其添加到历史路径中
                    if (history[car_id].back() != current_node) {
                        history[car_id].push_back(current_node);
                    }
                } else {
                    // 车辆还没有到达目的地，计划下一步移动
                    to_plan.push_back(car_id);
                }
            }
        }

        // 现在，为到达中间节点的车辆计划下一步移动
        for (int car_id : to_plan) {
            // 使用更新后的流量计划下一步路径
            vector<int> new_path = dijkstra(N, history[car_id].back(), cars[car_id][1], roadlength, flow, restrictions);
            if (new_path.size() == 0) {
                // 如果没有可用的路径，车辆等待下一个时间步
                event_queue.push(Event(current_time + 1, car_id, history[car_id].back()));
            } else {
                // 更新路径
                paths[car_id] = new_path;

                // 如果路径长度大于1，安排下一个移动事件
                if (paths[car_id].size() > 1) {
                    int u = paths[car_id][0];
                    int v = paths[car_id][1];
                    flow[u][v]++; // 更新流量
                    flow[v][u]++;
                    int travel_time = current_time + roadlength[u][v];
                    event_queue.push(Event(travel_time, car_id, v));

                    // 如果历史路径中还没有u，将其添加到历史路径中
                    if (history[car_id].back() != u) {
                        history[car_id].push_back(u);
                    }
                } else {
                    // 到达目的地
                    car_arrival_time[car_id] = current_time;

                    // 如果历史路径中还没有目的地，将其添加到历史路径中
                    if (history[car_id].back() != cars[car_id][1]) {
                        history[car_id].push_back(cars[car_id][1]);
                    }
                }
            }
        }

        // 清空to_plan列表，为下一个时间步做准备
        to_plan.clear();
    }

    // 输出每辆车的行驶路线
    for (int i = 0; i < M; i++) {
        cout << "Car " << i << " path: ";
        if (history[i][0] != cars[i][0]) cout << cars[i][0] + 1 << " "; // 输出起点
        for (int node : history[i]) {
            cout << node + 1; // 输出路径中的节点
            if (history[i][0] != cars[i][1]) cout << " ";
            else break;
        }

        // 打印每两个站台之间的距离
        cout << " Distances: ";
        for (size_t j = 1; j < history[i].size(); j++) {
            int u = history[i][j - 1];
            int v = history[i][j];
            cout << roadlength[u][v] << " ";
        }
        cout << endl;
    }

    // 输出总耗时
    int sum = 0;
    for (int i = 0; i < M; i++) {
        sum += car_arrival_time[i];
    }
    cout << "Total time: " << sum << endl;

    // 释放内存
    for (int i = 0; i < N; i++) {
        delete[] roadlength[i];
        delete[] restrictions[i];
        delete[] flow[i];
    }
    delete[] roadlength;
    delete[] restrictions;
    delete[] flow;
    for (int i = 0; i < M; i++) {
        delete[] cars[i];
    }
    delete[] cars;

    return 0;
}